// ---------------------------------------------------------------------
//
// Copyright (C) 2010 - 2018 by the deal.II authors
//
// This file is part of the deal.II library.
//
// The deal.II library is free software; you can use it, redistribute
// it, and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// The full text of the license can be found in the file LICENSE.md at
// the top level directory of deal.II.
//
// ---------------------------------------------------------------------


/**
 * @defgroup constraints Constraints on degrees of freedom
 * @ingroup dofs
 *
 * This module deals with constraints on degrees of
 * freedom. The central class to deal with constraints is the
 * AffineConstraints class.
 *
 * Constraints typically come from several sources, for example:
 * - If you have Dirichlet-type boundary conditions, $u|_{\partial\Omega}=g$,
 *   one usually enforces
 *   them by requiring that degrees of freedom on the boundary have
 *   particular values, for example $x_{12}=42$ if the boundary condition
 *   $g(\mathbf x)$ requires that the finite element solution $u(\mathbf x)$
 *   at the location of degree
 *   of freedom 12 has the value 42. Such constraints are generated by
 *   those versions of the VectorTools::interpolate_boundary_values
 *   function that take a AffineConstraints argument (though there are
 *   also other ways of dealing with Dirichlet conditions, using
 *   MatrixTools::apply_boundary_values, see for example step-3 and step-4).
 * - If you have boundary conditions that set a certain part of the
 *   solution's value, for example no normal flux, $\mathbf n \cdot
 *   \mathbf u=0$ (as happens in flow problems and is handled by the
 *   VectorTools::compute_no_normal_flux_constraints function) or
 *   prescribed tangential components, $\mathbf{n}\times\mathbf{u}=
 *   \mathbf{n}\times\mathbf{f}$ (as happens in electromagnetic problems and
 *   is handled by the VectorTools::project_boundary_values_curl_conforming
 *   function). For the former case, imagine for example that we are at
 *   at vertex where the normal vector has the form $\frac 1{\sqrt{14}}
 *   (1,2,3)^T$ and that the $x$-, $y$- and $z$-components of the flow
 *   field at this vertex are associated with degrees of freedom 12, 28,
 *   and 40. Then the no-normal-flux condition means that we need to have
 *   the condition $\frac 1{\sqrt{14}} (x_{12}+2x_{28}+3x_{40})=0$.
 *   The prescribed tangential component leads to similar constraints
 *   though there is often something on the right hand side.
 * - If you have hanging node constraints, for example in a mesh like this:
 *        @image html hanging_nodes.png ""
 *   Let's assume the bottom right one of the two red degrees of freedom
 *   is $x_{12}$ and that the two yellow neighbors on its left and right
 *   are $x_{28}$ and $x_{40}$. Then, requiring that the finite element
 *   function be continuous is equivalent to requiring that $x_{12}=
 *   \frac 12 (x_{28}+x_{40})$. A similar situation occurs in the
 *   context of hp adaptive finite element methods.
 *   For example, when using Q1 and Q2 elements (i.e. using
 *   FE_Q(1) and FE_Q(2)) on the two marked cells of the mesh
 *       @image html hp-refinement-simple.png
 *   there are three constraints: first $x_2=\frac 12 x_0 + \frac 12 x_1$,
 *   then $x_4=\frac 14 x_0 + \frac 34 x_1$, and finally the identity
 *   $x_3=x_1$. Similar constraints occur as hanging nodes even if all
 *   cells used the same finite elements. In all of these cases, you
 *   would use the DoFTools::make_hanging_node_constraints function to
 *   compute such constraints.
 * - Other linear constraints, for example when you try to impose a certain
 *   average value for a problem that would otherwise not have a unique
 *   solution. An example of this is given in the step-11 tutorial program.
 *
 * In all of these examples, constraints on degrees of freedom are linear
 * and possibly inhomogeneous. In other words, they always have
 * the form $x_{i_1} = \sum_{j=2}^M a_{i_j} x_{i_j} + b_i$. The deal.II
 * class that deals with storing and using these constraints is
 * AffineConstraints.
 *
 *
 * <h3>Eliminating constraints</h3>
 *
 * When building the global system matrix and the right hand sides, one can
 * build them without taking care of the constraints, i.e. by simply looping
 * over cells and adding the local contributions to the global matrix and
 * right hand side objects. In order to do actual calculations, you have to
 * 'condense' the linear system: eliminate constrained degrees of freedom and
 * distribute the appropriate values to the unconstrained dofs. This changes
 * the sparsity pattern of the sparse matrices used in finite element
 * calculations and is thus a quite expensive operation. The general scheme of
 * things is then that you build your system, you eliminate (condense) away
 * constrained nodes using the AffineConstraints::condense() functions, then
 * you solve the remaining system, and finally you compute the values of
 * constrained nodes from the values of the unconstrained ones using the
 * AffineConstraints::distribute() function. Note that the
 * AffineConstraints::condense() function is applied to matrix and right hand
 * side of the linear system, while the AffineConstraints::distribute()
 * function is applied to the solution vector. This is the method used in
 * the first few tutorial programs, see for example step-6.
 *
 * This scheme of first building a linear system and then eliminating
 * constrained degrees of freedom is inefficient, and a bottleneck if there
 * are many constraints and matrices are full, i.e. especially for 3d and/or
 * higher order or hp finite elements. Furthermore, it is impossible to
 * implement for %parallel computations where a process may not have access
 * to elements of the matrix. We therefore offer a second way of
 * building linear systems, using the
 * AffineConstraints::add_entries_local_to_global() and
 * AffineConstraints::distribute_local_to_global() functions discussed
 * below. The resulting linear systems are equivalent to those one gets after
 * calling the AffineConstraints::condense() functions.
 *
 * @note Both ways of applying constraints set the value of the matrix
 * diagonals to constrained entries to a <i>positive</i> entry of the same
 * magnitude as the other entries in the matrix. As a consequence, you need to
 * set up your problem such that the weak form describing the main matrix
 * contribution is not <i>negative definite</i>. Otherwise, iterative solvers
 * such as CG will break down or be considerably slower as GMRES.
 *
 * @note While these two ways are <i>equivalent</i>, i.e., the solution of
 * linear systems computed via either approach is the same, the linear
 * systems themselves do not necessarily have the same matrix and right
 * hand side vector entries. Specifically, the matrix diagonal and right hand
 * side entries corresponding to constrained degrees of freedom may be different
 * as a result of the way in which we compute them; they are, however, always
 * chosen in such a way that the solution to the linear system is the same.
 *
 * <h4>Condensing matrices and sparsity patterns</h4>
 *
 * As mentioned above, the first way of using constraints is to build linear
 * systems without regards to constraints and then "condensing" them away.
 * Condensation of a matrix is done in four steps:
 * - first one builds the
 *   sparsity pattern (e.g. using DoFTools::make_sparsity_pattern());
 * - then the sparsity pattern of the condensed matrix is made out of
 *   the original sparsity pattern and the constraints;
 * - third, the global matrix is assembled;
 * - and fourth, the matrix is finally condensed.
 *
 * In the condensation process, we are not actually changing the number of
 * rows or columns of the sparsity pattern, matrix, and vectors. Instead, the
 * condense functions add nonzero entries to the sparsity pattern of the
 * matrix (with constrained nodes in it) where the condensation process of the
 * matrix will create additional nonzero elements. In the condensation process
 * itself, rows and columns subject to constraints are distributed to the rows
 * and columns of unconstrained nodes. The constrained degrees of freedom
 * remain in place. In order not to
 * disturb the solution process, these rows and columns are filled with zeros
 * and an appropriate positive value on the main diagonal (we choose an
 * average of the magnitudes of the other diagonal elements, so as to make
 * sure that the new diagonal entry has the same order of magnitude as the
 * other entries; this preserves the scaling properties of the matrix). The
 * corresponding value in the right hand sides is set to zero. This way, the
 * constrained node will always get the value zero upon solution of the
 * equation system and will not couple to other nodes any more.
 *
 * Keeping the entries in the matrix has the advantage over creating a new and
 * smaller matrix, that only one matrix and sparsity pattern is
 * needed thus less memory is required. Additionally, the condensation process is
 * less expensive, since not all but only constrained values in the matrix
 * have to be copied. On the other hand, the solution process will take a bit
 * longer, since matrix vector multiplications will incur multiplications with
 * zeroes in the lines subject to constraints. Additionally, the vector size
 * is larger, resulting in more memory
 * consumption for those iterative solution methods using a larger number of
 * auxiliary vectors (e.g. methods using explicit orthogonalization
 * procedures).
 * Nevertheless, this process is more efficient due to its lower
 * memory consumption and is discussed in the first few programs
 * of the @ref Tutorial , for example in step-6.
 *
 * The condensation functions exist for different argument types: SparsityPattern,
 * SparseMatrix and
 * BlockSparseMatrix. Note that there are no versions for arguments of type
 * PETScWrappers::SparseMatrix() or any of the other PETSc or Trilinos
 * matrix wrapper classes. This is due to the fact that it is relatively
 * hard to get a representation of the sparsity structure of PETSc matrices,
 * and to modify them efficiently; this holds in particular, if the matrix is actually
 * distributed across a cluster of computers. If you want to use
 * PETSc/Trilinos matrices, you can either copy an already condensed deal.II
 * matrix, or assemble the PETSc/Trilinos matrix in the already condensed form,
 * see the discussion below.
 *
 *
 * <h5>Condensing vectors</h5>
 *
 * Condensing vectors works exactly as described above for matrices. Note that
 * condensation is an idempotent operation, i.e. doing it more than once on a
 * vector or matrix yields the same result as doing it only once: once an
 * object has been condensed, further condensation operations don't change it
 * any more.
 *
 * In contrast to the matrix condensation functions, the vector condensation
 * functions exist in variants for PETSc and Trilinos vectors. However,
 * using them is typically expensive, and should be avoided. You should use
 * the same techniques as mentioned above to avoid their use.
 *
 *
 * <h4>Avoiding explicit condensation</h4>
 *
 * Sometimes, one wants to avoid explicit condensation of a linear system
 * after it has been built at all. There are two main reasons for wanting to
 * do so:
 *
 * <ul>
 * <li>
 * Condensation is an expensive operation, in particular if there
 * are many constraints and/or if the matrix has many nonzero entries. Both
 * is typically the case for 3d, or high polynomial degree computations, as
 * well as for hp finite element methods, see for example the @ref hp_paper
 * "hp paper". This is the case discussed in the hp tutorial program, @ref
 * step_27 "step-27", as well as in step-22 and @ref step_31
 * "step-31".
 *
 * <li>
 * There may not be an AffineConstraints::condense() function for the matrix
 * you use (this is, for example, the case for the PETSc and Trilinos
 * wrapper classes where we have no access to the underlying representation
 * of the matrix, and therefore cannot efficiently implement the
 * AffineConstraints::condense() operation). This is the case discussed
 * in step-17, step-18, step-31, and step-32.
 * </ul>
 *
 * In this case, one possibility is to distribute local entries to the final
 * destinations right at the moment of transferring them into the global
 * matrices and vectors, and similarly build a sparsity pattern in the
 * condensed form at the time it is set up originally.
 *
 * The AffineConstraints class offers support for these operations as well. For
 * example, the AffineConstraints::add_entries_local_to_global() function adds
 * nonzero entries to a sparsity pattern object. It not only adds a given
 * entry, but also all entries that we will have to write to if the current
 * entry corresponds to a constrained degree of freedom that will later be
 * eliminated. Similarly, one can use the
 * AffineConstraints::distribute_local_to_global() functions to directly
 * distribute entries in vectors and matrices when copying local contributions
 * into a global matrix or vector. These calls make a subsequent call to
 * AffineConstraints::condense() unnecessary. For examples of their use see the
 * tutorial programs referenced above.
 *
 * Note that, despite their name which describes what the function really
 * does, the AffineConstraints::distribute_local_to_global() functions has to
 * be applied to matrices and right hand side vectors, whereas the
 * AffineConstraints::distribute() function discussed below is applied to the
 * solution vector after solving the linear system.
 *
 *
 * <h3>Distributing constraints</h3>
 *
 * After solving the condensed system of equations, the solution vector has to
 * be "distributed": the modification to the original linear system that
 * results from calling AffineConstraints::condense() leads to a linear system
 * that solves correctly for all degrees of freedom that are unconstrained but
 * leaves the values of constrained degrees of freedom undefined. To get the
 * correct values also for these degrees of freedom, you need to "distribute"
 * the unconstrained values also to their constrained colleagues. This is done
 * by the AffineConstraints::distribute() function.
 * The operation of distribution undoes the
 * condensation process in some sense, but it should be noted that it is not
 * the inverse operation. Basically, distribution sets the values of the
 * constrained nodes to the value that is computed from the constraint given
 * the values of the unconstrained nodes plus possible inhomogeneities.
 *
 *
 * <h3>Treatment of inhomogeneous constraints</h3>
 *
 * In case some constraint lines have inhomogeneities (which is typically the
 * case if the constraint comes from implementation of inhomogeneous boundary
 * conditions), the situation is a bit more complicated than if the only
 * constraints were due to hanging nodes alone. This is because the
 * elimination of the non-diagonal values in the matrix generate contributions
 * in the eliminated rows in the vector. This means that inhomogeneities can
 * only be handled with functions that act simultaneously on a matrix and a
 * vector. This means that all inhomogeneities are ignored in case the
 * respective condense function is called without any matrix (or if the matrix
 * has already been condensed before).
 *
 * The use of the AffineConstraints class for implementing Dirichlet
 * boundary conditions is discussed in the step-22 tutorial program. A
 * further example that utilizes AffineConstraints is step-41. The
 * situation here is little more complicated, because there we have some
 * constraints which are not at the boundary. There are two ways to apply
 * inhomogeneous constraints after creating an AffineConstraints object:
 *
 * First approach:
 * - Apply the AffineConstraints::distribute_local_to_global() function to the
 *   system matrix and the right-hand-side with the parameter
 *   use_inhomogeneities_for_rhs = false (i.e., the default)
 * - Set the solution to zero in the inhomogeneous constrained components
 *   using the AffineConstraints::set_zero() function (or start with a solution
 *   vector equal to zero)
 * - solve() the linear system
 * - Apply AffineConstraints::distribute() to the solution
 *
 * Second approach:
 * - Use the AffineConstraints::distribute_local_to_global() function with
 *   the parameter use_inhomogeneities_for_rhs = true and apply it to the
 *   system matrix and the right-hand-side
 * - Set the concerning components of the solution to the inhomogeneous
 *   constrained values (for example using AffineConstraints::distribute())
 * - solve() the linear system
 * - Depending on the solver now you have to apply the
 *   AffineConstraints::distribute() function to the solution, because the
 *   solver could change the constrained values in the solution. For a
 *   Krylov based solver this should not be strictly necessary, but it is
 *   still possible that there is a difference between the inhomogeneous
 *   value and the solution value in the order of machine precision, and
 *   you may want to call AffineConstraints::distribute() anyway if you
 *   have additional constraints such as from hanging nodes.
 *
 * Of course, both approaches lead to the same final answer but in different
 * ways. Using the first approach (i.e., when using
 * <code>use_inhomogeneities_for_rhs = false</code>
 * in AffineConstraints::distribute_local_to_global()), the linear system we
 * build has zero entries in the right hand side in all those places where a
 * degree of freedom is constrained, and some positive value on the matrix
 * diagonal of these lines. Consequently, the solution vector of the linear
 * system will have a zero value for inhomogeneously constrained degrees of
 * freedom and we need to call AffineConstraints::distribute() to give these
 * degrees of freedom their correct nonzero values.
 *
 * On the other hand, in the second approach, the matrix diagonal element and
 * corresponding right hand side entry for inhomogeneously constrained degrees
 * of freedom are so that the solution of the linear system already has the
 * correct value (e.g., if the constraint is that $x_{13}=42$ then row $13$ if
 * the matrix is empty with the exception of the diagonal entry, and
 * $b_{13}/A_{13,13}=42$ so that the solution of $Ax=b$ must satisfy
 * $x_{13}=42$ as desired). As a consequence, we do not need to call
 * AffineConstraints::distribute() after solving to fix up inhomogeneously
 * constrained components of the solution, though there is also no harm in
 * doing so.
 *
 * There remains the question of which of the approaches to take and why we
 * need to set to zero the values of the solution vector in the first
 * approach. The answer to both questions has to do with how iterative solvers
 * solve the linear system. To this end, consider that we typically stop
 * iterations when the residual has dropped below a certain fraction of the
 * norm of the right hand side, or, alternatively, a certain fraction of the
 * norm of the initial residual. Now consider this:
 *
 * - In the first approach, the right hand side entries for constrained
 *   degrees of freedom are zero, i.e., the norm of the right hand side
 *   really only consists of those parts that we care about. On the other
 *   hand, if we start with a solution vector that is not zero in
 *   constrained entries, then the initial residual is very large because
 *   the value that is currently in the solution vector does not match the
 *   solution of the linear system (which is zero in these components).
 *   Thus, if we stop iterations once we have reduced the initial residual
 *   by a certain factor, we may reach the threshold after a single
 *   iteration because constrained degrees of freedom are resolved by
 *   iterative solvers in just one iteration. If the initial residual
 *   was dominated by these degrees of freedom, then we see a steep
 *   reduction in the first step although we did not really make much
 *   progress on the remainder of the linear system in this just one
 *   iteration. We can avoid this problem by either stopping iterations
 *   once the norm of the residual reaches a certain fraction of the
 *   <i>norm of the right hand side</i>, or we can set the solution
 *   components to zero (thus reducing the initial residual) and iterating
 *   until we hit a certain fraction of the <i>norm of the initial
 *   residual</i>.
 * - In the second approach, we get the same problem if the starting vector
 *   in the iteration is zero, since then the residual may be
 *   dominated by constrained degrees of freedom having values that do not
 *   match the values we want for them at the solution. We can again
 *   circumvent this problem by setting the corresponding elements of the
 *   solution vector to their correct values, by calling
 *   AffineConstraints::distribute() <i>before</i> solving the linear system
 *   (and then, as necessary, a second time after solving).
 *
 * In addition to these considerations, consider the case where we have
 * inhomogeneous constraints of the kind $x_{3}=\tfrac 12 x_1 + \tfrac 12$,
 * e.g., from a hanging node constraint of the form $x_{3}=\tfrac 12 (x_1 +
 * x_2)$ where $x_2$ is itself constrained by boundary values to $x_2=1$.
 * In this case, the AffineConstraints container can of course not figure
 * out what the final value of $x_3$ should be and, consequently, can not
 * set the solution vector's third component correctly. Thus, the second
 * approach will not work and you should take the first.
 *
 *
 * <h3>Dealing with conflicting constraints</h3>
 *
 * There are situations where degrees of freedom are constrained in more
 * than one way, and sometimes in conflicting ways. Consider, for example
 * the following situation:
 *     @image html conflicting_constraints.png ""
 * Here, degree of freedom $x_0$ marked in blue is a hanging node. If we
 * used trilinear finite elements, i.e. FE_Q(1), then it would carry the
 * constraint $x_0=\frac 12 (x_{1}+x_{2})$. On the other hand, it is at
 * the boundary, and if we have imposed boundary conditions
 * $u|_{\partial\Omega}=g$ then we will have the constraint $x_0=g_0$
 * where $g_0$ is the value of the boundary function $g(\mathbf x)$ at
 * the location of this degree of freedom.
 *
 * So, which one will win? Or maybe: which one <i>should</i> win? There is
 * no good answer to this question:
 * - If the hanging node constraint is the one that is ultimately enforced,
 *   then the resulting solution does not satisfy boundary
 *   conditions any more for general boundary functions $g$.
 * - If it had been done the other way around, the solution would not satisfy
 *   hanging node constraints at this point and consequently would not
 *   satisfy the regularity properties of the element chosen (e.g. would not
 *   be continuous despite using a $Q_1$ element).
 * - The situation becomes completely hopeless if you consider
 *   curved boundaries since then the edge midpoint (i.e. the hanging node)
 *   does in general not lie on the mother edge. Consequently, the solution
 *   will not be $H^1$ conforming anyway, regardless of the priority of
 *   the two competing constraints. If the hanging node constraint wins, then
 *   the solution will be neither conforming, nor have the right boundary
 *   values.
 * In other words, it is not entirely clear what the "correct" solution would
 * be. In most cases, it will not matter much: in either case, the error
 * introduced either by the non-conformity or the incorrect boundary values
 * will be at worst at the same order as the discretization's overall error.
 *
 * That said, what should you do if you know what you want is this:
 * - If you want the hanging node constraints to win, then first build
 *   these through the DoFTools::make_hanging_node_constraints() function.
 *   Then interpolate the boundary values using
 *   VectorTools::interpolate_boundary_values() into the same
 *   AffineConstraints object. If the latter function encounters a boundary
 *   node that already is constrained, it will simply ignore the boundary
 *   values at this node and leave the constraint untouched.
 * - If you want the boundary value constraint to win, build the hanging
 *   node constraints as above and use these to assemble the matrix using
 *   the AffineConstraints::distribute_local_to_global() function (or,
 *   alternatively, assemble the matrix and then use
 *   AffineConstraints::condense() on it). In a second step, use the
 *   VectorTools::interpolate_boundary_values() function that returns
 *   a std::map and use it as input for MatrixTools::apply_boundary_values()
 *   to set boundary nodes to their correct value.
 *
 * Either behavior can also be achieved by building two separate
 * AffineConstraints objects and calling AffineConstraints::merge()
 * function with a particular second argument.
 *
 *
 * <h3>Applying constraints indirectly with a LinearOperator</h3>
 *
 * Sometimes it is either not desirable, or not possible to directly
 * condense, or eliminate constraints from a system of linear equations. In
 * particular if there is no underlying matrix object that could be
 * condensed (or taken care of constraints during assembly). This is
 * usually the case if the system is described by a LinearOperator.
 *
 * In this case we can solve the modified system
 * @f[
 *   (C^T A C + Id_c) \tilde x = C^T (b - A\,k)
 * @f]
 * instead [1] (M. S. Shephard. Linear multipoint constraints applied via
 * transformation as part of a direct stiffness assembly process.
 * <i>International Journal for Numerical Methods in Engineering</i>
 * 20(11):2107-2112, 1985).
 *
 * Here, $A$ is a given (unconstrained) system matrix for which we only
 * assume that we can apply it to a vector but can not necessarily access
 * individual matrix entries. $b$ is the corresponding right hand side of a
 * system of linear equations $A\,x=b$. The matrix $C$ describes the
 * homogeneous part of the linear constraints stored in an
 * AffineConstraints object and the vector $k$ is the vector of
 * corresponding inhomogeneities. More precisely, the
 * AffineConstraints::distribute() operation applied on a vector $x$ is the
 * operation
 * @f[
    x \leftarrow C\,x+k.
 * @f]
 * And finally, $Id_c$ denotes the identity on the subspace of constrained
 * degrees of freedom.
 *
 * The corresponding solution of $A\,x=b$ that obeys these constraints is
 * then recovered by distributing constraints: $x=C\tilde x+k$.
 *
 * The whole system can be set up and solved with the following snippet of
 * code:
 * @code
 * #include <deal.II/lac/constrained_linear_operator.h>
 *
 * // ...
 *
 * // system_matrix      - unconstrained and assembled system matrix
 * // right_hand_side    - unconstrained and assembled right hand side
 * // affine_constraints - an AffineConstraints object
 * // solver             - an appropriate, iterative solver
 * // preconditioner     - a preconditioner
 *
 * const auto op_a = linear_operator(system_matrix);
 * const auto op_amod = constrained_linear_operator(affine_constraints, op_a);
 * Vector<double> rhs_mod = constrained_right_hand_side(affine_constraints,
 *                                                      op_a,
 *                                                      right_hand_side);
 *
 * solver.solve(op_amod, solution, rhs_mod, preconditioner);
 * affine_constraints.distribute(solution);
 * @endcode
 */
